package LeetCode;

import java.util.TreeSet;

public class LC_358_RearrangeStringkDistanceApart {

    public static void main(String[] args) {

    }

    static class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int m = matrix.length;
            int n = matrix[0].length;
            int result = Integer.MIN_VALUE;
            for (int c1 = 0; c1 < n; c1++) {
                int[] each = new int[m];
                for (int c2 = c1; c2 >= 0; c2--) {
                    for (int r = 0; r < m; r++) each[r] += matrix[r][c2];
                    result = Math.max(result, getLargestSumCloseToK(each, k));
                }
            }
            return result;
        }

        int getLargestSumCloseToK(int[] arr, int k) {
            int sum = 0;
            TreeSet<Integer> set = new TreeSet<>();
            int result = Integer.MIN_VALUE;
            set.add(0);
            for (int anArr : arr) {
                sum = sum + anArr;
                Integer ceiling = set.ceiling(sum - k);
                if (ceiling != null) result = Math.max(result, sum - ceiling);
                set.add(sum);
            }
            return result;
        }
    }

    static class Solution_2 {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int row = matrix.length;
            int col = matrix[0].length;
            int m = Math.max(row, col);
            int n = Math.min(row, col);
            boolean isRowLarger = false;
            if (row > col) isRowLarger = true;
            int result = Integer.MIN_VALUE;
            for (int c1 = 0; c1 < n; c1++) {
                int[] each = new int[m];
                for (int c2 = c1; c2 >= 0; c2--) {
                    for (int r = 0; r < m; r++) each[r] += isRowLarger ? matrix[r][c2] : matrix[c2][r];
                    result = Math.max(result, getLargestSumCloseToK(each, k));
                }
            }
            return result;
        }

        int getLargestSumCloseToK(int[] arr, int k) {
            int sum = 0;
            TreeSet<Integer> set = new TreeSet<>();
            int result = Integer.MIN_VALUE;
            set.add(0);
            for (int anArr : arr) {
                sum = sum + anArr;
                Integer ceiling = set.ceiling(sum - k);
                if (ceiling != null) result = Math.max(result, sum - ceiling);
                set.add(sum);
            }
            return result;
        }

    }

}